package operations;
public class Tree<E> {
	private TSTNode<E> theRoot;
	private int defaultNumReturnValues = -1;
	private int lastNumberOfReturnValues;
	public void save(String key, E value) {
		getOrCreateNode(key).data = value;
	}
	protected TSTNode<E> getOrCreateNode(String key) throws NullPointerException, IllegalArgumentException {
		if(theRoot == null) theRoot = new TSTNode<E>(key.charAt(0), null);
		TSTNode<E> currentNode=theRoot;
		int charIndex=0;
		while (true) {
			int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if(charIndex == key.length()) return currentNode;
				if(currentNode.relatives[TSTNode.EQKID] == null) currentNode.relatives[TSTNode.EQKID] = new TSTNode<E>(key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if(charComp < 0) {
				if(currentNode.relatives[TSTNode.LOKID] == null) currentNode.relatives[TSTNode.LOKID] = new TSTNode<E>(key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {                
				if(currentNode.relatives[TSTNode.HIKID] == null) currentNode.relatives[TSTNode.HIKID] = new TSTNode<E>(key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}
	public TSTNode<E> getNode(String key) {
		return getNode(key, theRoot);
	}
	protected TSTNode<E> getNode(String key, TSTNode<E> startNode) {
		if(key == null || startNode == null || key.length() == 0) return null;
		TSTNode<E> currentNode = startNode;
		int charIndex = 0;
		while(true) {
			if(currentNode == null) return null;
			int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if(charIndex == key.length()) return currentNode;
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if(charComp < 0) {
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}
	public Object get(String key) {
		TSTNode<E> node = getNode(key);
		if(node==null) return null;
		return node.data;
	}
	public void remove(String key) {
		deleteNode(getNode(key));
	}
	public void setNumReturnValues(int num) {
		defaultNumReturnValues = (num < 0) ? -1 : num;
	}	
	private int checkNumberOfReturnValues(int numReturnValues) {
		return ((numReturnValues < 0) ? -1 : numReturnValues);
	}
	public int getLastNumReturnValues() {
		return lastNumberOfReturnValues;
	}
	public DoublyLinkedList matchPrefix(String prefix) {
		return matchPrefix(prefix, defaultNumReturnValues);
	}
	public DoublyLinkedList matchPrefix(String prefix, int numReturnValues) {
		sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		sortKeysResult = new DoublyLinkedList();
		TSTNode<E> startNode = getNode(prefix);
		if(startNode == null) return sortKeysResult;
		if(startNode.data != null) {
			sortKeysResult.addLast(getKey(startNode));
			sortKeysNumReturnValues--;
		}
		sortKeysList = true;
		sortKeysRecursion(startNode.relatives[TSTNode.EQKID]);
		return sortKeysResult;
	}
	public String matchPrefixString(String prefix) {
		return matchPrefixString(prefix, defaultNumReturnValues);
	}
	public String matchPrefixString(String prefix, int numReturnValues) {
		TSTNode<E> startNode = getNode(prefix);
		if(startNode == null) return "";
		sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		lastNumberOfReturnValues = sortKeysNumReturnValues;
		sortKeysBuffer = new StringBuffer();
		if(startNode.data != null) {
			sortKeysBuffer.append(getKey(startNode) + "\n");
			sortKeysNumReturnValues--;
		}
		sortKeysList = false;
		sortKeysRecursion(startNode.relatives[TSTNode.EQKID]);
		int bufferLength = sortKeysBuffer.length();
		if(bufferLength > 0) sortKeysBuffer.setLength(bufferLength - 1); // delete the final \n
		lastNumberOfReturnValues = lastNumberOfReturnValues - sortKeysNumReturnValues;
		return sortKeysBuffer.toString();
	}
	private DoublyLinkedList sortKeysResult;		// convenience variable for matchPrefix and sortKeys methods
	private boolean sortKeysList;		// convenience variable for matchPrefix, matchPrefixString and sortKeys methods
	private StringBuffer sortKeysBuffer;		// convenience variable for matchPrefixString and sortKeys methods
	private int sortKeysNumReturnValues;			// convenience variable for matchPrefix and sortKeys methods	
	private void sortKeysRecursion(TSTNode<E> currentNode) {
		if(currentNode == null) return;
		sortKeysRecursion(currentNode.relatives[TSTNode.LOKID]);
		if(sortKeysNumReturnValues == 0) return;
		if(currentNode.data != null) {
			if(sortKeysList) {
				sortKeysResult.addLast(getKey(currentNode));
			} else {
				sortKeysBuffer.append(getKey(currentNode) + "\n");
			}
			sortKeysNumReturnValues--;
		}
		sortKeysRecursion(currentNode.relatives[TSTNode.EQKID]);
		sortKeysRecursion(currentNode.relatives[TSTNode.HIKID]);
	}
	protected DoublyLinkedList sortKeys(TSTNode<E> startNode, int numReturnValues) {
		sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		sortKeysResult = new DoublyLinkedList();
		sortKeysRecursion(startNode);
		return sortKeysResult;
	}
	public String sortKeysString(int numReturnValues) {
		return sortKeysString(theRoot, numReturnValues);
	}
	public String sortKeysString() {
		return sortKeysString(theRoot, defaultNumReturnValues);
	}
	public String sortKeysString(TSTNode<E> startNode, int numReturnValues) {
		if(startNode == null) return new String("");
		sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		lastNumberOfReturnValues = sortKeysNumReturnValues;
		sortKeysBuffer = new StringBuffer();
		if(startNode.data != null) {
			sortKeysBuffer.append(getKey(startNode) + "\n");
			sortKeysNumReturnValues--;
		}
		sortKeysList = false;
		sortKeysRecursion(startNode);
		int bufferLength = sortKeysBuffer.length();
		if(bufferLength > 0) sortKeysBuffer.setLength(bufferLength - 1); // delete the final \n
		lastNumberOfReturnValues = lastNumberOfReturnValues - sortKeysNumReturnValues;
		return sortKeysBuffer.toString();
	}
	private DoublyLinkedList matchAlmostResult;		// convenience variable for matchAlmost
	private StringBuffer matchAlmostBuffer;		// convenience variable for matchAlmostString
	private boolean matchAlmostListAction;			// convenience variable for matchAlmost and matchAlmostString
	private int matchAlmostNumReturnValues;			// convenience variable for matchAlmost
	private String matchAlmostKey;			// convenience variable for matchAlmost
	private int matchAlmostDiff;				// convenience variable for matchAlmost
	private int maxMatchAlmostDiff = 4;				// convenience variable for matchAlmost
	public DoublyLinkedList matchAlmost(String key) {
		return matchAlmost(key, defaultNumReturnValues);
	}
	protected DoublyLinkedList matchAlmost(String key, int numReturnValues) {
		matchAlmostListAction = true;
		matchAlmostNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		matchAlmostResult = new DoublyLinkedList();
		matchAlmostKey = key;
		matchAlmostRecursion(theRoot, 0, matchAlmostDiff);
		return matchAlmostResult;
	}
	public String matchAlmostString(String key) {
		return matchAlmostString(key, defaultNumReturnValues);
	}
	protected String matchAlmostString(String key, int numReturnValues) {
		matchAlmostListAction = false;
		matchAlmostNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		lastNumberOfReturnValues = matchAlmostNumReturnValues;
		matchAlmostBuffer = new StringBuffer();
		matchAlmostKey = key;
		matchAlmostRecursion(theRoot, 0, matchAlmostDiff);
		int bufferLength = matchAlmostBuffer.length();
		if(bufferLength > 0) matchAlmostBuffer.setLength(bufferLength - 1); // delete the final \n
		lastNumberOfReturnValues = lastNumberOfReturnValues - matchAlmostNumReturnValues;
		return matchAlmostBuffer.toString();
	}
	private void matchAlmostRecursion(TSTNode<E> currentNode, int charIndex, int d) {
		if((currentNode == null) || (d < 0) || (matchAlmostNumReturnValues == 0) || (charIndex >= matchAlmostKey.length())) return;
		int charComp = compareCharsAlphabetically(matchAlmostKey.charAt(charIndex), currentNode.splitchar);
		if((d > 0) || (charComp < 0)) matchAlmostRecursion(currentNode.relatives[TSTNode.LOKID], charIndex, d);		
		int nextD = (charComp == 0) ? d : d - 1;
		if((matchAlmostKey.length() == charIndex + 1) && (nextD == 0) && (currentNode.data != null)) {
			if(matchAlmostListAction) {
				matchAlmostResult.addLast(getKey(currentNode));
			} else {
				matchAlmostBuffer.append(getKey(currentNode) + "\n");
			}
			matchAlmostNumReturnValues--;
		}
		matchAlmostRecursion(currentNode.relatives[TSTNode.EQKID], charIndex + 1, nextD);
		// hi branch
		if((d > 0) || (charComp > 0)) matchAlmostRecursion(currentNode.relatives[TSTNode.HIKID], charIndex, d);
	}
	public void setMatchAlmostDiff(int diff) {
		if(diff < 0) {
			matchAlmostDiff = 0;
		} else if (diff > maxMatchAlmostDiff) {
			matchAlmostDiff = maxMatchAlmostDiff;
		} else {
			matchAlmostDiff = diff;
		}
	}
	
	private void deleteNode(TSTNode<E> nodeToDelete) {
		if(nodeToDelete == null) return;
		nodeToDelete.data = null;
		while(nodeToDelete != null) {
			nodeToDelete = deleteNodeRecursion(nodeToDelete);
		}
	}
	private TSTNode<E> deleteNodeRecursion(TSTNode<E> currentNode) {
		if(currentNode == null) return null;
		if(currentNode.relatives[TSTNode.EQKID] != null || currentNode.data != null) return null;  // can't delete this node if it has a non-null eq kid or data	
		TSTNode<E> currentParent = currentNode.relatives[TSTNode.PARENT];
		boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
		boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;
		int childType;
		if(currentParent.relatives[TSTNode.LOKID] == currentNode) {
			childType = TSTNode.LOKID;
		} else if(currentParent.relatives[TSTNode.EQKID] == currentNode) {
			childType = TSTNode.EQKID;
		} else if(currentParent.relatives[TSTNode.HIKID] == currentNode) {
			childType = TSTNode.HIKID;
		} else {
			theRoot = null;
			return null;
		}
	
		if(lokidNull && hikidNull) {
			currentParent.relatives[childType] = null;
			return currentParent;
		}
		if(lokidNull) {
			currentParent.relatives[childType] = currentNode.relatives[TSTNode.HIKID];
			currentNode.relatives[TSTNode.HIKID].relatives[TSTNode.PARENT] = currentParent;
			return currentParent;
		}
		if(hikidNull) {
			currentParent.relatives[childType] = currentNode.relatives[TSTNode.LOKID];
			currentNode.relatives[TSTNode.LOKID].relatives[TSTNode.PARENT] = currentParent;
			return currentParent;
		}
		int deltaHi = currentNode.relatives[TSTNode.HIKID].splitchar - currentNode.splitchar;
		int deltaLo = currentNode.splitchar - currentNode.relatives[TSTNode.LOKID].splitchar;
		int movingKid;
		TSTNode<E> targetNode;
		if(deltaHi == deltaLo) {
			if(Math.random() < 0.5) {
				deltaHi++;
			} else {
				deltaLo++;
			}
		}
		
		if(deltaHi > deltaLo) {
			movingKid = TSTNode.HIKID;
			targetNode = currentNode.relatives[TSTNode.LOKID];
		} else {
			movingKid = TSTNode.LOKID;
			targetNode = currentNode.relatives[TSTNode.HIKID];
		}
		
		while(targetNode.relatives[movingKid] != null) targetNode = targetNode.relatives[movingKid];
		targetNode.relatives[movingKid] = currentNode.relatives[movingKid];
		currentParent.relatives[childType] = targetNode;
		targetNode.relatives[TSTNode.PARENT] = currentParent;
		if(!lokidNull) currentNode.relatives[TSTNode.LOKID] = null;
		if(!hikidNull) currentNode.relatives[TSTNode.HIKID] = null;
		return currentParent;
	}
	private StringBuffer getKeyBuffer = new StringBuffer();   // convenience variable for getKey method
	protected String getKey(TSTNode<E> node) {
		getKeyBuffer.setLength(0);
		getKeyBuffer.append(node.splitchar);
		TSTNode<E> currentNode, lastNode;
		currentNode = node.relatives[TSTNode.PARENT];
		lastNode = node;
		while(currentNode != null) {
			if(currentNode.relatives[TSTNode.EQKID] == lastNode) getKeyBuffer.append(currentNode.splitchar);
			lastNode = currentNode;
			currentNode = currentNode.relatives[TSTNode.PARENT];
		}
		getKeyBuffer.reverse();
		return getKeyBuffer.toString();
	}

	private int numNodes;   // convenience variable for numNodes methods
	private boolean checkData;   // convenience variable for numNodes methods
	public int numNodes() {
		return numNodes(theRoot);
	}
	protected int numNodes(TSTNode<E> startingNode) {
		numNodes = 0;
		checkData = false;
		recursiveNodeCalculator(startingNode);
		return numNodes;
	}
	public int numDataNodes() {
		return numDataNodes(theRoot);
	}
	protected int numDataNodes(TSTNode<E> startingNode) {
		numNodes = 0;
		checkData = true;
		recursiveNodeCalculator(startingNode);
		return numNodes;
	}	
	private void recursiveNodeCalculator(TSTNode<E> currentNode) {
		if(currentNode == null) return;
		recursiveNodeCalculator(currentNode.relatives[TSTNode.LOKID]);
		recursiveNodeCalculator(currentNode.relatives[TSTNode.EQKID]);
		recursiveNodeCalculator(currentNode.relatives[TSTNode.HIKID]);
		if(checkData) {
			if(currentNode.data != null) numNodes++;
		} else {
			numNodes++;
		}
	}
	public static int compareCharsAlphabetically(char cCompare, char cRef) {
		return (alphabetizeChar(cCompare) - alphabetizeChar(cRef));
	}
	private static int alphabetizeChar(char c) {
		if(c < 65) return c;
		if(c < 89) return (2 * c) - 65;
		if(c < 97) return c + 24;
		if(c < 121) return (2 * c) - 128;
		return c;
	}
}